package airthmetic.exercise.stack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

// 单调递减栈 + 哨兵
public class _84_柱状图中最大的矩形 {

   /* 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

    求在该柱状图中，能够勾勒出来的矩形的最大面积。*/
    public static int largestRectangleArea(int[] heights) {
//        int max = 0;
//        if(heights == null || heights.length == 0){
//            return max;
//        }
//        int[] h = new int[heights.length + 2];
//        h[0] = -1;
//        h[heights.length - 1] = -1;
//        System.arraycopy(heights,0,h,1, heights.length);
//        Deque<Integer> deque = new ArrayDeque<>();
//        deque.push(0);
//        for(int i=1; i<h.length; i++){
//            while(h[i] < h[deque.peek()]){
//                int height = h[deque.pop()];
//                int area = height * (i - deque.peek() - 1);
//                max = Math.max(max, area);
//            }
//            deque.push(i);
//        }
//        return max;


        int max = 0;
        if(heights == null || heights.length == 0){
            return max;
        }

        int[] nums = new int[heights.length + 2];
        nums[0] = -1;
        nums[nums.length -1] = -1;
        System.arraycopy(heights, 0, nums, 1, heights.length);
        Stack<Integer> stack = new Stack<>();
        stack.push(0);

        for(int i=1; i< nums.length; i++){
            while(nums[i] < nums[stack.peek()]){
                int heigth = nums[stack.pop()];
                max = Math.max(max, (heigth * (i - stack.peek() - 1)));
            }
            stack.push(i);
        }
        return max;

    }

    public static void main(String[] args) {
//        int[] heights = new int[]{3,5,1
//                                ,1,1,1
//                                ,1,1,1,
//                                1};

        int[] heights = new int[]{2,1,5,6,2,3};


        System.out.println(largestRectangleArea(heights));

    }
}
